#pragma once
// 使用邻接链表表示的无向图

/*
    1. 无向图中没有自连边
    2. 在无向图中, 任意两个不相同的顶点之间至多有一条边
    3. 在无向图中, 不存在两个编号相同的顶点
*/
#include <vector>
using std::vector;

#include "chain_table.h"

struct vertex
{
    int m_number; // 顶点的编号, 从1开始

    vertex(int num = 0);

    // 比较
    bool operator==(const vertex &x);
    bool operator!=(const vertex &x);
    bool operator<(const vertex &x);
    bool operator<=(const vertex &x);
    bool operator>(const vertex &x);
    bool operator>=(const vertex &x);
};

class undigraph
{
public:
    // 初始化成零图, 默认是一个空图. 
    undigraph(int vertex_count = 0);

    // 添加一条边 (a, b)
    void insert(int a, int b);

    // 判断无向边(a, b)是否存在, 存在返回true, 不存在返回false
    bool isexist_edge(int a, int b);

    // 删除一条边 (a, b)
    void erase(int a, int b);

    /*
        广度优先搜索bfs, 确定一个顶点的可达的顶点集, 可达顶点集包含它本身
        @v: 字典序最小的bfs顶点访问序列
    */
    void BFS(int num, vector<int> &v);

    /*
        深度优先搜索dfs, 确定一个顶点的可达的顶点集, 可达顶点集包含它本身
        @v: 字典序最小的dfs顶点访问序列
    */
    void DFS(int num, vector<int> &v);

    // 为了应付题目要求所写的特定的有关连通分支的函数, 结果依靠所传的参数进行返回
    void connected_components_info(int &res_num, vector<int> &res_min_sequence);

    /*
        最短路径, 使用Dijkstra
        存在最短路径, 返回长度; 不存在, 返回-1
    */
    int shortest_path_Dijkstra(int s, int d);

private:
    vector<chain_table<vertex>> m_adjacency_linked_list;
    int m_vertex_count;
    int m_edge_count;

    /*
        广度优先搜索bfs, 确定一个顶点的可达的顶点集, 可达顶点集包含它本身
        @v: 字典序最小的bfs顶点访问序列, 传一个空vector
        @sign: 大小必须为m_vertex_count+1
    */
    void BFS(int num, vector<int> &v, vector<bool> &sign);

    /*
        深度优先搜索dfs, 确定一个顶点的可达的顶点集, 可达顶点集包含它本身
        @v: 字典序最小的dfs顶点访问序列, 传一个空vector
        @sign: 大小必须为m_vertex_count+1
    */
    void DFS(int num, vector<int> &v, vector<bool> &sign);

    /*
        得到所有的连通分支
        @res: 中的每一个数组记录了一个连通分支的所有顶点数, 传一个空的vector<vector<int>>
    */
    void get_all_connected_components(vector<vector<int>> &res);

    /*
        Dijkstra算法
        在调用这个函数时, 先把这三个数组进行初始化, 再传参
        @visited 全初始化成false
        @distance 全初始化成-1, 表示未知
        @prev 全初始化成-1, 表示未知
    */
    void single_source_shortest_paths(int start, vector<bool> &visited, vector<int> &distance, vector<int> &prev);
};
